﻿// homework3_2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 100

double h = 0;

typedef struct {
    char SOURCECODE;        //不同的字符
    int NUM;                //不同字符出现的次数
    double PROBABILITY;     //不同字符出现的频率
    int Code[MAX];          //huffman编码符号
    int start;
    int parent;             //huffman树父节点
    int lchild;             //huffman树左子节点
    int rchild;             //huffman树右子节点
    int LengthofHuffmanCode;//huffman编码长度
}Hcode;
Hcode INFORMATION[MAX];

int Pofeachsource(char informationsource[MAX], int a) {     //求字符串包含的字符及其次数和频率函数
    int i, j = 1, m, flag = 0;
    char temp;      
    //先存入第一个字符，用于与后续字符作比较，统计不同的字符存入结构体数组，利用flag标记某字符是否出现过
    INFORMATION[0].SOURCECODE = informationsource[0];       //存入输入字符串的第一个字母
    for (i = 1; i < a; i++) {
        for (m = 0; m < i; m++) {
            flag = 0;
            if (informationsource[m] == informationsource[i]) {     //遇到相同字母
                flag = 1;   //flag标记置1
                break;
            }
        }
        if (flag == 1)
            continue;
        else
            INFORMATION[j++].SOURCECODE = informationsource[i];
    }
    INFORMATION[j].SOURCECODE = '\0';
    //printf("字符串中的字符数为%d\n", j);
    //统计相同字符出现的次数，每统计一个字符NUM清零
    for (i = 0; i < j; i++) {
        INFORMATION[i].NUM = 0;
        for (m = 0; m < a; m++)
            if (informationsource[m] == INFORMATION[i].SOURCECODE)
                INFORMATION[i].NUM++;
    }
    //统计每个字符出现的概率
    for (i = 0; i < j; i++)
        INFORMATION[i].PROBABILITY = (float)INFORMATION[i].NUM / a;
    //打印每个字符的出现次数和频率
    for (i = 0; i < j; i++)
        //printf("%c:%.2f\n", INFORMATION[i].SOURCECODE, INFORMATION[i].PROBABILITY);
    return j;
}

void Huffman(int a) {   //Huffman编码函数
    Hcode cd;
    int i, j, m = 0, lm = 0, p, c;
    double min, lmin;
    for (i = 0; i < a; i++) {
        INFORMATION[i].parent = -1;
        INFORMATION[i].lchild = -1;
        INFORMATION[i].lchild = -1;
    }
    //循环构造Huffman树
    for (i = 0; i < a - 1; i++) {
        //min和lmin存两个没有父节点且权值最小的两个节点
        min = lmin = MAX;
        //找到所有结点中无父节点权值最小的两个节点，合并成为一棵二叉树
        for (j = 0; j < a + i; j++) {
            if ((INFORMATION[j].PROBABILITY < min) && (INFORMATION[j].parent == -1)) {
                lmin = min;
                lm = m;
                min = INFORMATION[j].PROBABILITY;
                m = j;
            }
            else if ((INFORMATION[j].PROBABILITY < lmin) && (INFORMATION[j].parent == -1)) {
                lmin = INFORMATION[j].PROBABILITY;
                lm = j;
            }
        }
        //设置找到的两个节点m和lm的父节点的信息
        INFORMATION[m].parent = a + i;
        INFORMATION[lm].parent = a + i;
        INFORMATION[a + i].PROBABILITY = INFORMATION[m].PROBABILITY + INFORMATION[lm].PROBABILITY;
        INFORMATION[a + i].parent = -1;
        INFORMATION[a + i].lchild = m;
        INFORMATION[a + i].rchild = lm;
    }
    for (i = 0; i < a; i++) {   //从第0个结点开始遍历
        cd.start = a - 1;       //a个结点最多用到a-1位数码
        c = i;                          //c记录此节点的编号
        p = INFORMATION[c].parent;      //p记录该节点的父节点编号
        while (p != -1) {               //父节点存在
            if (INFORMATION[p].lchild == c)     //如果此节点是左子节点
                cd.Code[cd.start] = 0;  //分配数码0
            else                                //如果此节点是右子节点
                cd.Code[cd.start] = 1;  //分配数码1
            cd.start--;         //继续求编码的上一位
            c = p;              //c转去记录父节点
            p = INFORMATION[c].parent;  //p记录c节点的父节点，上升继续分配编码
        }
        for (j = cd.start + 1; j < a; j++) {
            INFORMATION[i].Code[j] = cd.Code[j];
        }
        INFORMATION[i].start = cd.start;
    }
}

int main()
{
    //定义存放字符串的数组
    Hcode temp;
    char informationsource[MAX];
    int i, j, m, k;
    for (i = 0;; i++) {
        scanf("%c", &informationsource[i]);
        if (informationsource[i] == '\n')
            break;
    }
    informationsource[i] = '\0';
    //返回不同字符的数目
    m = Pofeachsource(informationsource, i);
    //输出Huffman编码
    Huffman(m);
    for (k = 0; k < m - 1; k++) {
        for (i = 0; i < m - k - 1; i++) {
            if (INFORMATION[i].PROBABILITY < INFORMATION[i + 1].PROBABILITY) {
                temp = INFORMATION[i];
                INFORMATION[i] = INFORMATION[i + 1];
                INFORMATION[i + 1] = temp;
            }
        }
    }
    for (i = 0; i < m; i++) {
        printf("%c:%.2f:", INFORMATION[i].SOURCECODE, INFORMATION[i].PROBABILITY);
        for (j = INFORMATION[i].start + 1; j < m; j++)
            printf("%d", INFORMATION[i].Code[j]);
        INFORMATION[i].LengthofHuffmanCode = m - INFORMATION[i].start - 1;
        printf("\n");
    }
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
